package 地图软件的最短路径算法;


import java.util.Arrays;
import java.util.LinkedList;

/**
 * 我们刚提到的最优问题包含三个：最短路线、最少用时和最少红绿灯。
 * 我们先解决最简单的，最短路线。
 * 解决软件开发中的实际问题，最重要的一点就是建模，也就是将复杂的场景抽象成具体的数据结构。
 * 针对这个问题，我们该如何抽象成数据结构呢？我们之前也提到过，图这种数据结构的表达能力很强，显然，把地图抽象成图最合适不过了。
 * 我们把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。
 * 如果路是单行道，我们就在两个顶点之间画一条有向边；
 * 如果路是双行道，我们就在两个顶点之间画两条方向不同的边。
 * 这样，整个地图就被抽象成一个有向有权图。具体的代码实现，我放在下面了。
 * 于是，我们要求解的问题就转化为，在一个有向有权图中，求两个顶点间的最短路径。
 */
public class Graph {//有向有权图的邻接矩阵表示

    /**
     * 图中顶点的个数
     */
    private int v;

    /**
     * 邻接矩阵
     */
    private LinkedList<Edge>[] adj;


    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<Edge>();
        }
    }

    public void addEdge(int start,int end,int weight){
       adj[start].add(new Edge(start, end, weight));
    }

    private class Edge{//图中的边

        /**
         * 起始点编号
         */
        private int start;

        /**
         * 结束点编号
         */
        private int end;

        /**
         * 权重
         */
        private int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    // 下面这个类是为了dijkstra实现用的
    private class Vertex {
        public int id; // 顶点编号ID

        public int dist; // 从起始顶点到这个顶点的距离

        public Vertex(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "id=" + id +
                    ", dist=" + dist +
                    '}';
        }
    }

    //自己实现一个优先级队列(一个小顶堆)
    private class PriorityQueue{

        //小顶堆的一维数组表现形式
        private Vertex[] nodes;

        //堆的大小
        private int n;

        //当前堆有多少数据
        private int count;

        public PriorityQueue(int n) {
            //方便计算,多申请一个空间
            nodes = new Vertex[n+1];
            this.n = n;
            count = 0;
        }

        //模拟出队操作
        public Vertex poll(){
            if (isEmpty()){
                System.out.println("队空");
                throw new NullPointerException();
            }
            Vertex result = nodes[1];
            //重新堆化
            Vertex node = nodes[count];
            nodes[count] = null;
            count--;
            nodes[1] = node;
            int cur = 1;
            while (true){
                int minPos = cur;
                if (2*cur <= count && node.dist > nodes[2*cur].dist){
                    minPos = 2*cur;
                }
                if (2*cur+1 <= count && nodes[minPos].dist > nodes[2*cur+1].dist){
                    minPos = 2*cur+1;
                }
                if (minPos == cur){
                    break;
                }
                swap(cur,minPos );
                cur = minPos;
            }
            return result;
        }

        public void update(Vertex vertex){
            for (int i = 1; i <= count; i++) {
                if (nodes[i].id == vertex.id){
                    nodes[i].dist = vertex.dist;
                    int cur = i;
                    while (cur>=2){
                        if (vertex.dist < nodes[cur/2].dist){
                            swap(cur,cur/2 );
                            cur /= 2;
                        }else {
                            nodes[cur] = vertex;
                            break;
                        }
                    }
                    break;
                }
            }

        }

        //模拟入队操作
        public void add(Vertex vertex){
            if (isFull()){
                System.out.println("队满");
                throw new RuntimeException("队满");
            }
            if (isEmpty()){
                nodes[1] = vertex;
                count++;
                return;
            }
            count++;
            int cur = count;
            nodes[cur] = vertex;
            while (cur>=2){
                if (vertex.dist < nodes[cur/2].dist){
                    swap(cur,cur/2 );
                    cur /= 2;
                }else {
                    nodes[cur] = vertex;
                    break;
                }
            }

        }

        public boolean isEmpty(){
            return count == 0;
        }

        public boolean isFull(){
            return count == n;
        }

        public void swap(int n,int m){
            Vertex temp = nodes[n];
            nodes[n] = nodes[m];
            nodes[m] = temp;
        }

    }


    public  void test() {
        Vertex vertex2 = new Vertex(2, 2);
        Vertex vertex1 = new Vertex(1, 1);
        Vertex vertex3 = new Vertex(3, 3);
        Vertex vertex4 = new Vertex(4, 4);
        Vertex vertex5 = new Vertex(5, 5);
        Vertex vertex6 = new Vertex(6, 6);
        Vertex vertex7 = new Vertex(7, 7);
        Vertex vertex8 = new Vertex(8, 8);
        Vertex vertex9 = new Vertex(9, 9);

        PriorityQueue priorityQueue = new PriorityQueue(10);
        priorityQueue.add(vertex2);
        priorityQueue.add(vertex1);
        priorityQueue.add(vertex3);
        priorityQueue.add(vertex5);
        priorityQueue.add(vertex6);
        priorityQueue.add(vertex7);
        priorityQueue.add(vertex8);
        priorityQueue.add(vertex9);
        vertex9.dist = -1;
        priorityQueue.update(vertex9);
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());

    }

    public void dijkstra(int s,int t){//s到t的最短路径
        int[] predecessor = new int[v];//用来还原最短路径
        Vertex[] vertices = new Vertex[v];
        for (int i = 0; i < v; i++) {
            vertices[i] = new Vertex(i,Integer.MAX_VALUE );
        }
        PriorityQueue queue = new PriorityQueue(v);
        boolean[] inqueue = new boolean[v];
        vertices[s].dist = 0;
        queue.add(vertices[s]);
        inqueue[s] = true;
        while (!queue.isEmpty()){
            Vertex poll = queue.poll();
            int id = poll.id;
            if (id == t){
                break;
            }
            LinkedList<Edge> edges = adj[id];
            for (Edge edge : edges) {
                if (vertices[id].dist + edge.weight < vertices[edge.end].dist){
                    vertices[edge.end].dist = vertices[id].dist + edge.weight;
                    predecessor[edge.end] = id;
                    if (inqueue[edge.end] == true){
                        queue.update(vertices[edge.end]);
                    }else {
                        queue.add(vertices[edge.end]);
                        inqueue[edge.end] = true;
                    }
                }
            }
        }
        System.out.print(s);
        print(s, t, predecessor);


    }

    private void print(int s, int t, int[] predecessor) {
        if (s==t){
            return;
        }
        print(s,predecessor[t] ,predecessor );
        System.out.print("->" + t);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(7);
        graph.addEdge(1, 2, 10);
        //graph.addEdge(1, 5, 15);
        //graph.addEdge(2, 3, 15);
        //graph.addEdge(2, 4, 2);
        //graph.addEdge(4, 3, 1);
        //graph.addEdge(4, 6, 12);
        //graph.addEdge(3, 6, 5);
        //graph.addEdge(5, 6, 10);
        //graph.dijkstra(1,6 );
        int a = -20;
        int b = 30;
        int result1 = a << 1;
        int result2 = a >> 1;
        int result3 = a >>> 1;
        int result4 = a & b;
        int result5 = a | b;
        int result6 = a ^ b;
        int result7 = ~ a;
        System.out.println(result1);
        System.out.println(result2);
        System.out.println(result3);
        System.out.println(result4);
        System.out.println(result5);
        System.out.println(result6);
        System.out.println(result7);
        System.out.println(Integer.MAX_VALUE);
    }
}
